'''
线段树
区间add
区间query
'''


from typing import List

class SegmentTree:
    def __init__(self, nums: List[int]):
        self.n = n = len(nums)
        # sum info 数组
        self.S = [0] * (n << 2)
        # lazy add 数组
        self.A = [0] * (n << 2)
        self._build(nums)

    def _build(self, nums):
        def f(l, r, root):
            if l == r:
                self.S[root] = nums[l-1]
            else:
                mid = (l + r) >> 1
                f(l, mid, root << 1)
                f(mid + 1, r, root << 1 | 1)
                self._up(root)

        f(1, len(nums), 1)  # 区间[1, n], root节点1

    def _up(self, root):
        self.S[root] = self.S[root << 1] + self.S[root << 1 | 1]

    def _down(self, l, r, root):
        if self.A[root]:
            mid = (l + r) >> 1
            self._lazy(l, mid, root << 1, self.A[root])
            self._lazy(mid + 1, r, root << 1 | 1, self.A[root])
            self.A[root] = 0

    def _lazy(self, l, r, root, v):
        self.S[root] += v * (r - l + 1)
        self.A[root] += v

    def add(self, L, R, V):
        def f(l, r, root):
            if r < L or l > R: return       # 没这个区间的事情
            if L <= l <= r <= R:            # 如果任务区间，包含了当前区间。直接蓝更新
                self._lazy(l, r, root, V)
                return
            # 包含了一部分当前区间，那只能下发了。懒更新内容要下发
            self._down(l, r, root)
            mid = (l + r) >> 1
            f(l, mid, root << 1)
            f(mid + 1, r, root << 1 | 1)
            # 子节点更新完毕了，要更新当前节点的值
            self._up(root)

        f(1, self.n, 1)

    def query(self, L, R):
        def f(l, r, root):
            # same case like add
            if r < L or l > R: return 0
            if L <= l <= r <= R:
                return self.S[root]
            # 包含了一部分当前区间，还要往下分别收集，且要考虑懒更新内容
            self._down(l, r, root)
            mid = (l + r) >> 1
            return f(l, mid, root << 1) + f(mid + 1, r, root << 1 | 1)
        return f(1, self.n, 1)